# 32. 最长有效括号
class Solution:
    def longestValidParentheses(self, s: str) -> int:
        n = len(s)

        @cache
        def valid(left, right):
            stack = deque()
            for i in range(left, right + 1):
                if s[i] == '(':
                    stack.append(s[i])
                elif len(stack) == 0:
                    return False
                else:
                    stack.pop()
            return len(stack) == 0

        @cache
        def dfs(i, j):
            if i >= j:
                return 0
            elif valid(i, j):
                return j - i + 1
            return max(dfs(i + 1, j), dfs(i, j - 1))

        return dfs(0, n - 1)
